from typing import List


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        return max(self.maxCoinLi(nums))

    def maxCoinLi(self, nums):
        length = len(nums)
        if length == 1:
            return [nums[0]]

        r = []
        for i in range(length):
            if i == 0:
                r = r + [nums[0] * nums[1] +
                         x for x in self.maxCoinLi(nums[1:])]
            elif i == length - 1:
                r = r + [nums[length - 2] + nums[length - 1] +
                         x for x in self.maxCoinLi(nums[:-1])]
            else:
                r = r + [nums[i - 1] * nums[i] * nums[i + 1] +
                         x for x in self.maxCoinLi(nums[:i] + nums[i+1:])]
        return r


# print(Solution().maxCoins([3,1,5,8]))
print(Solution().maxCoins([9,76,64,21,97,60,5])) # 卧槽，怎么排查？


